package cn.rocky.structures.queue;

/**
 * 优先队列(延迟队列采用的排序方式)
 * 底层数据实现上数组,但体现形式是一颗二叉堆树结构。在元素存放时,
 * 通过对存放元素的比较和替换形成二叉堆结构。
 * 1. 父子节点索引关系
 *      a. 假如父节点为 queue[n], 那么左子节点为 queue[2n + 1], 右子节点为 queue[2n+2]
 *      b. 任意孩子节点的父节点位置, 都是 n-1>>>1 相当于除2取整
 * 2. 节点间大小关心
 *      a. 父节点小于等于任意孩子节点
 *      b. 同一层级的两个孩子节点大小不需要维护,它是在弹出元素的时候进行判断的
 * 3. 子叶节点与非子叶节点
 *      a. 一个长度为 size 的优先级队列, 当 index >= size >>> 1, 该节点为叶子节点。
 *      否则,为非叶子节点。
 * @param <E>
 */
public class PriorityQueue<E> implements Queue<E> {

    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    transient Object[] queue;

    private int size = 0;

    public PriorityQueue() {
        this.queue = new Object[DEFAULT_INITIAL_CAPACITY]; // 默认初始化容量
    }

    @Override
    public boolean add(E e) {
        return offer(e);
    }

    @Override
    public boolean offer(E e) {
        if (e == null) {
            throw new NullPointerException();
        }
        int i = size;
        if (i > queue.length) { // 队列大小大于当前队列中已有元素大小
            // 扩容
        }
        // 入队 先增加已有元素数量
        size = i + 1;
        if (i == 0) { // 未被初始化, 元素添加到第0号位置
            queue[0] = e;
        } else {
            siftUp(i , e);
        }
        return true;
    }

    /**
     *
     * @param k 未添加该元素时 队列大小
     * @param x 要被添加的元素
     */
    private void siftUp(int k, E x) {
        siftUpComparable(k, x);
    }

    /**
     * 入队操作(二叉堆的存放元素时, 以遵循它的特点,
     * 会在存放过程中,通过队尾元素向上比对迁移)
     * @param k 未添加该元素时 队列大小
     * @param x 要被添加的元素
     */
    @SuppressWarnings("unchecked")
    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            // 获取父节点Idx，相当于除以2
            int parent = (k - 1) >>> 1; // 无符号右移位
            System.out.println("【入队】寻找当前节点的父节点位置。k："
                    + k + " parent：" + parent);
            Object e = queue[parent]; // 获取父节点
            // 如果当前位置元素，大于父节点元素，则退出循环
            if (key.compareTo((E) e) >= 0) {
                System.out.println("【入队】值比对，父节点："
                        + e.toString()+" 目标节点："
                        + key.toString());
                break;
            }
            // 相反父节点位置大于当前位置元素，则进行替换
            System.out.println("【入队】替换过程，父子节点位置替换，继续循环。父节点值："
                    + e.toString()+ " 存放到位置："
                    + k);
            queue[k] = e;  // 新增加的位置为父节点
            k = parent;    // k = 父节点位置
        }
        queue[k] = key;    // 入队元素 在父节点处
        System.out.println("【入队】完成 Idx：" + k + "Val：" + key + "\r\n当前队列：" + queue.toString());
    }


    @Override
    public E poll() {
        if (size == 0) {
            return null;
        }
        int s = --size;
        E result = (E)queue[0];
        E x = (E)queue[s];
        queue[s] = null;
        if (s != 0) {
            siftDown(0, x);
        }
        return result;
    }

    private void siftDown(int k, E x) {
        siftDownComparable(k, x);
    }

    /**
     * 出队操作: 只要把根元素直接删除弹出即可。
     * 接着需要在根元素迁移走后,寻找另外的最小元素迁移到对头。
     * 这个过程与入队正好相反,这是一个不断向下迁移的过程。
     * @param k 队头元素
     * @param x 队尾元素
     */
    @SuppressWarnings("unchecked")
    private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        // 先找出中间节点
        int half = size >>> 1;
        while (k < half) {
            // 找到左子节点和右子节点，两个节点进行比较，找出最大的值
            int child = (k << 1) + 1;
            Object c = queue[child];
            int right = child + 1;
            // 左子节点与右子节点比较，取最小的节点
            if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) {
                System.out.println("【出队】左右子节点比对，获取最小值。" +
                        "left：" + c.toString()+ " right:" + queue[right].toString());
                c = queue[child = right];
            }
            // 目标值与c比较，当目标值小于c值，退出循环。说明此时目标值所在位置适合，迁移完成。
            if (key.compareTo((E) c) <= 0) {
                break;
            }
            // 目标值小于c值，位置替换，继续比较
            System.out.println("【出队】替换过程，节点的值比对。上节点：" +
                    queue[k].toString() +" 下节点：" + c.toString()+ "位置替换");
            queue[k] = c;
            k = child;
        }
        // 把目标值放到对应位置
        System.out.println("【出队】替换结果，最终更换位置。" +
                "Idx：" + k + "Val：" + key.toString());
        queue[k] = key;
    }

    @Override
    public E peek() {
        return (size == 0) ? null :(E)queue[0];
    }

}
